from typing import List


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if matrix == [] or matrix[0] == []:
            return []

        def add(a,b):
            return (a[0]+b[0], a[1]+b[1])
        
        def minus(a,b):
            return (a[0]-b[0], a[1]-b[1])
        
        directions = [(0,1),(1,0),(0,-1),(-1,0)]
        visited = {(0,0)}
        res = [matrix[0][0]]
        next_ = (0,0)
        t = 0
        m,n = len(matrix), len(matrix[0])
        while len(res) < m*n:
            next_ = add(next_, directions[t])
            while next_ not in visited and((0 <= next_[0] < m) and (0 <= next_[1] <n)) :
                ele = matrix[next_[0]][next_[1]]
                res.append(ele)
                visited.add(next_)
                next_= add(next_, directions[t])
            next_ = minus(next_, directions[t])
            t = (t+1) % 4
        return res
    
if __name__ == '__main__':
    s = Solution()
    m = [[1,2,3],[4,5,6],[7,8,9]]
    print(s.spiralOrder(m))